package com.yoshino.leetcode.oneHundred.seventh;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null) {
            return false;
        }
        if (B == null) {
            return false;
        }
        // 从 A 中深度遍历，找到第一个 B 等于根结点的
        return back(A, B);
        // 深度遍历 B 看是否匹配
    }

    private boolean back(TreeNode root, TreeNode match) {
        if (root == null) {
            return false;
        }
        boolean flag = false;
        if (root.val == match.val) {
            // 深度遍历 B 看是否匹配
            flag = backMatch(root, match);
        }
        if (!flag && root.left != null) {
            flag = back(root.left, match);
        }
        if (!flag && root.right != null) {
            flag = back(root.right, match);
        }
        return flag;
    }

    private boolean backMatch(TreeNode root, TreeNode match) {
        if (match == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        boolean flag = true;
        if (root.val != match.val) {
            // 深度遍历 B 看是否匹配
            return false;
        }
        if (flag && match.left != null) {
            flag = backMatch(root.left, match.left);
        }
        if (flag && match.right != null) {
            flag = backMatch(root.right, match.right);
        }
        return flag;
    }

    public TreeNode mirrorTree(TreeNode root) {
        // 层序遍历
        // 对于一个结点，即 交换左右子结点 即可
        if (root == null) {
            return root;
        }
        TreeNode res = root, temp;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }
            temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
        return res;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return idMetric(root.left, root.right);
    }

    private boolean idMetric(TreeNode first, TreeNode second) {
        if (first == null && second == null) {
            return true;
        }
        if (first == null || second == null) {
            return false;
        }
        return first.val == second.val && idMetric(first.left, second.right) && idMetric(first.right, second.left);
    }
}